package demo.practice.uf;

import java.util.HashSet;
import java.util.Set;

public class P130 {

    public void solve(char[][] board) {
        UF uf = new UF(board);
    }

    class UF {
        int[] parent;
        int[] rank;//树的层数


        public UF(char[][] board) {
            if (board == null || board.length == 0 || board[0].length == 0)
                return;

            int h = board.length;
            int w = board[0].length;
            parent = new int[h * w];
            rank = new int[h * w];
            Set<Integer> sides = new HashSet<>();

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (board[i][j] == 'O') {
                        parent[w * i + j] = w * i + j;
                        rank[w * i + j] = 1;
                        if (i - 1 >= 0 && board[i - 1][j] == 'O') {
                            join(w * i + j, w * (i - 1) + j);
                        }
                        if (j - 1 >= 0 && board[i][j - 1] == 'O') {
                            join(w * i + j, w * i + j - 1);
                        }

                        if (i == 0 || j == 0 || i == h - 1 || j == w - 1) {
                            //边缘元素
                            sides.add(findP(w * i + j));
                        }
                    }
                }
            }

            Set<Integer> fps = new HashSet<>();
            for (Integer sp : sides) {
                fps.add(findP(sp));
            }


            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (board[i][j] == 'O' && !fps.contains(findP(w * i + j))) {
                        board[i][j] = 'X';
                    }
                }
            }
        }


        public int findP(int x) {
            if (x < 0 || x >= parent.length)
                return -1;  //或者直接抛出异常
            while (parent[x] != x)//一直搜索到根节点
                x = parent[x];
            return x;
        }

        public void join(int a, int b) {
            int ap = findP(a);
            int bp = findP(b);
            if (ap != bp) {
                //a的层数越高，就将层数少的合并到层数高的上面
                if (rank[ap] > rank[bp])
                    parent[bp] = ap;
                else if (rank[ap] < rank[bp]) {
                    parent[ap] = bp;
                } else {
                    //相同情况的话，随便就可以
                    parent[ap] = bp;
                    rank[bp]++;
                }
            }
        }
    }

}
